package ai.zixing.mashibing.basic_class.class12;

/**
 * 背包问题的动态规划解法
 */
public class Code03_Knapsack {

    public static int getMaxValue(int[] w, int[] v, int bag) {
        return process(w, v, 0, bag);
    }

    // 只剩下rest的空间了，
    // index...货物自由选择，但是不要超过rest的空间
    // 返回能够获得的最大价值
    public static int process(int[] w, int[] v, int index, int rest) {
        // base case 1
        if (rest <= 0) {
            return -1;
        }
        // base case2
        if (index == w.length) {
            return 0;
        }
        // 有货物也有空间
        int p1 = process(w, v, index + 1, rest);
        int p2 = -1;
        if (rest >= w[index]) {
            p2 = v[index] + process(w, v, index + 1, rest - w[index]);
        }
        return Math.max(p1, p2);
    }

    // 动态规划
    // 暴力递归的过程就是决策转移
    public static int dpWay(int[] w, int[] v, int bag) {
        int N = w.length;
        int[][] dp = new int[N + 1][bag + 1];
        // dp[N][...] = 0, java 默认值是 0
        // N 行填完了，从 N-1 行开始填到 0 行
        for (int index = N - 1; index >= 0; index--) {
            // 剩余空间从 1 到 bag
            for (int rest = 1; rest <= bag; rest++) {
                dp[index][rest] = dp[index + 1][rest];
                // 同暴力递归的逻辑，如下
                int p1 = dp[index + 1][rest];
                int p2 = -1;
//                int p2Next = dp[index + 1][rest - w[index]];
                // 要保证 rest - w[index] 有效
                if (rest - w[index] >= 0) {
                    p2 = v[index] + dp[index + 1][rest - w[index]];
                }
                dp[index][rest] = Math.max(p1, p2);
            }
        }
        return dp[0][bag];
    }

    public static void main(String[] args) {
        int[] weights = {3, 2, 4, 7};
        int[] values = {5, 6, 3, 19};
        int bag = 11;
        System.out.println(getMaxValue(weights, values, bag));
        System.out.println(dpWay(weights, values, bag));
    }
}
